
\section{Funcionamiento de motores comerciales}

Comenzaremos estudiando el mecanismo utilizado por los Buffer Managers de dos motores de bases de datos comerciales: \textbf{Oracle} y \textbf{PostgreSQL}.

% TODO chequear apostrofe
En realidad estos motores no revelan en su documentaci\'on los detalles de su funcionamiento interno. Sin embargo existen ciertas publicaciones al respecto por parte de personas que trabajaron en esos proyectos, y tambi\'en por parte de quienes analizaron el c\'odigo fuente, en el caso de PostgreSQL que es Open Source. Nosotros basamos nuestro an\'alisis en el art\'iculo \textit{All about Oracle's touch count algorithm} de Craig A. Shallahamer y en la presentaci\'on \textit{Inside de PostgreSQL shared buffer cache} de Greg Smith.

\subsection{Oracle}

\subsubsection{LRU est\'andar}

En un principio, el algoritmo de reemplazo de p\'aginas utilizado por Oracle era un \textbf{LRU est\'andar}. Es decir, se eleg\'ia como v\'ictima, entre los bloques que no estaban en uso, a aqu\'el cuya \'ultima referencia era la m\'as antigua. Cabe señalar que como referencia se cuentan tanto los \textbf{pin} (solicitud) como los \textbf{unpin} (liberaci\'on).

Esto se implementa con una lista de punteros a los bloques del buffer, cuyos extremos se llaman \textit{extremo LRU} y \textit{extremo MRU}. Cada vez que se añade un nuevo bloque al buffer, se lo inserta en el extremo MRU, y cada vez que son referenciados se los mueve a este extremo. As\'i, naturalmente van movi\'endose hacia el otro extremo los bloques que no son referenciados hace tiempo. As\'i que a la hora de elegir una v\'ictima se busca desde el extremo LRU.

\subsubsection{LRU modificado}

Notemos que con esta estrategia un \textbf{file scan} que involucre m\'as bloques que los disponibles en el buffer, barrer\'a con todo los bloques que estaban cacheados ocupando el buffer innecesariamente, porque el scan nunca vuelve atr\'as. Para salvar esto en cierto momento se modific\'o el algoritmo, convirti\'endose en el llamado \textbf{LRU modificado}: ahora los bloques correspondientes a un file scan se agregan en el extremo LRU, solucion\'andose el problema. El resultado es que durante un file scan los sucesivos bloques explorados van desalojando al anterior, sin interferir con el resto del buffer.

\subsubsection{M\'ultiples buffers}

Sin embargo sigue sucediendo que bloques de distinta naturaleza interfieren entre s\'i, por lo cual en Oracle se decidi\'o la utilizaci\'on de \textbf{m\'ultiples buffers}. Se trata de tres pools fijos:

\begin{itemize}
\item \textbf{keep pool}: utilizado para objetos pequeños que siempre deber\'ian estar en memoria
\item \textbf{recycle pool}: utilizado para objetos grandes, evitando que interfieran con el resto
\item \textbf{default pool}: utilizado para todo lo dem\'as
\end{itemize}

\subsubsection{Touch-count}

El motor estuvo siempre en evoluci\'on, y lleg\'o el momento de refinar a\'un m\'as el mecanismo. Los motivos que impulsaban un cambio eran el tamaño creciente de los buffers y los requerimientos de mayor performance y control del buffer. Esto \'ultimo significa que no s\'olo se desea un mecanismo que sea satisfactorio en el caso general, sino que adem\'as sea flexible y pueda ser \textit{tuneado} para cada caso particular.

As\'i surgi\'o el algoritmo \textbf{touch-count}. En primer lugar, la parte de la lista de punteros que est\'a m\'as cercana al extremo LRU se llama \textit{parte fr\'ia} (que contiene los \textit{buffers fr\'ios}. La otra es la \textit{parte caliente}. En general la divisi\'on es en la mitad de la lista, pero esto puede ser configurado en otra proporci\'on.

Cuando un bloque nuevo es añadido al buffer, se inserta en el l\'imite entre las dos partes, es decir en medio de la lista. Ya no se lo inserta en el extremo MRU, porque el bloque todav\'ia no ha demostrado merecer tal lugar (podr\'ia ser que no vuelva a ser referenciado). En caso de ser referenciado muchas veces, podr\'a ganar el acceso al extremo privilegiado.

Por otra parte, para cada bloque cacheado se mantiene un contador, y cada vez que es referenciado se incrementa el contador, en lugar de mover el bloque como se hac\'ia antes.	 En realidad s\'olo se incrementa el contador una vez cada 3 segundos (valor configurable) para evitar contar muchas veces las referencias repetidas.

El movimiento de bloques dentro de la lista se produce cuando se busca una v\'ictima para desalojar. Se van recorriendo los bloques desde el extremo LRU, y cada bloque que se encuentra cuyo contador es mayor a 2 (configurable) se mueve al extremo MRU y se resetea a 0.
Esto produce que un bloque caliente (el m\'as fr\'io entre ellos) se mueva a la parte fr\'ia. A \'este se le resetea el contador a 1.

\subsection{PostgreSQL}

En PostgreSQL se utiliza un mecanismo m\'as simple de explicar pero cuyo funcionamiento no parece distar tanto del de Oracle. Se trata del algoritmo del reloj generalizado.

El algoritmo b\'asico del reloj (tambi\'en llamado \textit{segunda oportunidad}) consiste en disponer los bloques en una lista circular, y tener siempre un puntero apuntando a uno de ellos (la manecilla del reloj). Para cada bloque se almacena un bit, que empieza valiendo 1. Cada vez que se debe seleccionar uno como v\'ictima, se va moviendo el puntero en orden hasta encontrar uno con el bit en 0. Los que se atraviesan con el bit en 1, son reseteados a 0. Por \'ultimo, cada vez que se referencia un bloque se setea su bit en 1.

De esta manera, los bloques que son referenciados sobrevivir\'an a la siguiente pasada de la manecilla, pero para sobrevivir una nueva pasada deber\'an ser referenciados nuevamente.

La generalizaci\'on de este mecanismo consiste en reemplazar los bits por contadores. Se inicializan en cero, se incrementan en cada referencia y se decrementan en cada pasada de la manecilla. Cuando la manecilla encuentra uno en 0, se lo toma como v\'ictima. PostgreSQL utiliza este algoritmo con un tope de 5 como m\'aximo valor del contador.

\subsection{Comparaci\'on}

Ambos motores utilizan mecanismos similares, en el sentido de que mantienen un contador de referencias con el que se dan una idea de la frecuencia de utilizaci\'on del bloque en el pasado. Esta frecuencia es considerada como una aproximaci\'on a la frecuencia de acceso en el futuro de acuerdo al criterio de cercan\'ia temporal.

Dos ventajas que podemos señalar del mecanismo de Oracle son el tratamiento independiente de los file scans (tambi\'en contemplado por PostgreSQL a partir de la versi\'on 8.3) y la utilizaci\'on de buffers m\'ultiples. Adem\'as cuenta con m\'as par\'ametros variables, lo cual implica una mayor flexibilidad. En la pr\'actica esto permite ir probando diferentes configuraciones y elegir la que m\'as convenga para nuestra aplicaci\'on espec\'ifica.

Del mecanismo de PostgreSQL destacamos la simplicidad, lo que puede ser una gran ventaja para quien est\'e encargado de tunear los par\'ametros del Buffer Manager.

